#include<iostream>
#include<string>
#include<queue>
using namespace std;

struct AVLnode {
	int key;
	int height;
	AVLnode* left;
	AVLnode* right;

	AVLnode(int K) {
		key = K;
		height = 0;
		left = right = NULL;
	}
};

int getHeight(AVLnode* T) {
	return (T == NULL) ? -1 : T->height;
}

int max(int a, int b) {
	return (a > b) ? a : b;
}

void updateHeight(AVLnode* T) {
	T->height = max(getHeight(T->left), getHeight(T->right)) + 1;
}

void LL(AVLnode*& A) {
	AVLnode* B = A->left;
	A->left = B->right;
	B->right = A;
	updateHeight(A);
	updateHeight(B);
	A = B;
}

void RR(AVLnode*& A) {
	AVLnode* B = A->right;
	A->right = B->left;
	B->left = A;
	updateHeight(A);
	updateHeight(B);
	A = B;
}

void LR(AVLnode*& A) {
	RR(A->left);
	LL(A);
}

void RL(AVLnode*& A) {
	LL(A->right);
	RR(A);
}

int flagIn = 0; //int flag = 0;
int InsertAVL(AVLnode*& T, int K, int level) {
	//int flag = 0;
	if (T == NULL) {
		T = new AVLnode(K);
	}
	else if (K < T->key) {
		flagIn |= InsertAVL(T->left, K, level + 1);
	}
	else if (K > T->key) {
		flagIn |= InsertAVL(T->right, K, level + 1);
	}
	if (getHeight(T->left) - getHeight(T->right) == 2) {
		if (!flagIn) {
			printf("Insert ");
			printf("%d", K);
			printf(": ");
		}
		flagIn = 1;
		printf("Reblance subtree rooted at node ");
		printf("%d ", T->key);
		printf("on level ");
		printf("%d ", level);
		if (getHeight(T->left->left) >= getHeight(T->left->right)) {
			LL(T);
			printf("with right rotation. ");
		}
		else {
			LR(T);
			printf("with left rotation and right rotation. ");
		}
	}
	else if (getHeight(T->right) - getHeight(T->left) == 2) {
		if (!flagIn) {
			printf("Insert ");
			printf("%d", K);
			printf(": ");
		}
		flagIn = 1;
		printf("Reblance subtree rooted at node ");
		printf("%d ", T->key);
		printf("on level ");
		printf("%d ", level);
		if (getHeight(T->right->right) >= getHeight(T->right->left)) {
			RR(T);
			printf("with left rotation. ");
		}
		else {
			RL(T);
			printf("with right rotation and left rotation. ");
		}
	}
	updateHeight(T);
	return flagIn;
}

int flagre = 0; int num = 0;
int remove(AVLnode*& T, int K, int level) {
	//int flag = 0;
	if (T == NULL) {
		return 0;
	}
	if (K < T->key) {
		flagre |= remove(T->left, K, level + 1);
	}
	else if (K > T->key) {
		flagre |= remove(T->right, K, level + 1);
	}
	else if (T->left != NULL && T->right != NULL) {
		AVLnode* next = T->right;
		while (next->left != NULL) {
			next = next->left;
		}
		T->key = next->key;
		flagre |= remove(T->right, next->key, level + 1);
	}
	else {
		AVLnode* before = T;
		T = (T->left != NULL) ? T->left : T->right;
		delete before;
	}

	if (T != NULL) {
		if (getHeight(T->left) - getHeight(T->right) == 2) {
			if (!flagre) {
				printf("Remove ");
				printf("%d", num);
				printf(": ");
			}
			flagre = 1;
			printf("Reblance subtree rooted at node ");
			printf("%d ", T->key);
			printf("on level ");
			printf("%d ", level);
			if (getHeight(T->left->left) >= getHeight(T->left->right)) {
				LL(T);
				printf("with right rotation. ");
			}
			else {
				LR(T);
				printf("with left rotation and right rotation. ");
				//if (flag) printf(" ");
				//else printf("\n");
				//flag = 1;
			}
		}
		else if (getHeight(T->right) - getHeight(T->left) == 2) {
			if (!flagre) {
				printf("Remove ");
				printf("%d", num);
				printf(": ");
			}
			flagre = 1;
			printf("Reblance subtree rooted at node ");
			printf("%d ", T->key);
			printf("on level ");
			printf("%d ", level);
			if (getHeight(T->right->right) >= getHeight(T->right->left)) {
				RR(T);
				printf("with left rotation. ");
			}
			else {
				RL(T);
				printf("with right rotation and left rotation. ");
			}
		}
		updateHeight(T);
	}
	return flagre;
}

void printDLR(AVLnode* T) {
	if (T != NULL) {
		printf("%d ", T->key);
		printDLR(T->left);
		printDLR(T->right);
	}
}
void printLDR(AVLnode* T) {
	if (T != NULL) {
		printLDR(T->left);
		printf("%d ", T->key);
		printLDR(T->right);
	}
}

int main() {
	int n;//cin>>n;
	scanf("%d", &n);
	AVLnode* T = NULL;
	int flagall = 0;

	while (n--) {
		char str[10];
		int K;

		scanf("%s %d", str, &K);
		flagIn = 0;
		flagre = 0;
		//flag = 0;
		if (str[0] == 'I') {
			//flagIn = 0;
			flagall |= InsertAVL(T, K, 0);
			if (InsertAVL(T, K, 0)) {
				printf("\n");
			}
		}
		else {
			num = K;
			flagall |= remove(T, K, 0);
			if (remove(T, K, 0)) {
				printf("\n");
			}
		}
	}
	if (flagall) {
		printf("\n");
	}
	printLDR(T);
	printf("\n\n");
	printDLR(T);
	//printf("\n");

	//system("pause");
	return 0;

}
